Dizionario
TERMINE:> Macchine di Turing
lunedì 9 novembre 1998
AUTORE:> Turing
FONTE:>
Elliott Mendelson, Second Thoughts about Church's Thesis and Mathematical Proofs, "The Journal of Philosophy", vol. LXXXVII, 1990, p.227
Una macchina di Turing è costituita, innanzitutto, da un nastro diviso in riquadri (il nastro consiste, in ogni dato momento, di un numero finito di riquadri, benché, quando risulti necessario, ulteriori riquadri possano sempre essere aggiunti a destra o a sinistra del nastro), in cui sono stampati dei simboli (in un riquadro può trovarsi al massimo un simbolo), scelti da un insieme finito di simboli costituenti l'alfabeto della macchina, e uno scanner che le consente di osservare il contenuto di un solo riquadro alla volta. Ad ogni istante, lo scanner può trovarsi in uno qualsiasi dei suoi stati interni, anch'essi costituenti una collezione finita.
La macchina di Turing ha inoltre un programma, ossia una lista finita di istruzioni che le dicono cosa fare a seconda dei casi. Essa può compiere, a partire da uno stato iniziale e secondo le istruzioni del suo programma, le seguenti azioni : (1) sostituire il simbolo, che in quell'istante sta osservando, con un altro simbolo, che può essere anche lo stesso; (2) spostarsi di un riquadro a destra; (3) spostarsi di un riquadro a sinistra; (4) fermarsi. Una volta compiuta l'azione appropriata, il programma determina il nuovo stato interno dello scanner.
All'inizio del processo di computazione di una funzione di n argomenti, gli n argomenti si trovano scritti sul nastro separati da un riquadro vuoto: poiché ciascuno di questi n argomenti è un numero naturale, ciascun numero naturale m si trova sul nastro sotto forma di una sequenza di m+1 tratti, | | | …|, stampati su riquadri consecutivi.
Quando, dopo aver eseguito il programma, la macchina si ferma e sul nastro rimane la rappresentazione di un dato numero naturale k, k è allora considerato il valore della funzione computata.
ASSUNZIONI;